''' 3 - Intelligence artificielle''' '''3-2 - Algorithme k-moyennes''' ## 3-2 - Algorithme k-moyennes ## Imports from random import uniform as rdu from random import randint as rdi from matplotlib import pyplot as plt import math import numpy as np plt.close('all') ## Création des données 2D G = 5 # Nombre de groupes PPG = 65 # Nombre de points par groupes NP = G*PPG # Nombre de points Largeur = 2 # Largeur groupe +- Lx_2D = [] for g in range(G): X0 = rdi(10,90) Y0 = rdi(10,90) for p in range(PPG): X = X0 + rdi(-Largeur,Largeur) Y = Y0 + rdi(-Largeur,Largeur) Pt = [X,Y] Lx_2D.append(Pt) def Affiche_2D(fig,LL,Col): ''' Affiche chaque liste de la liste LL avec la couleur respective de la liste Col ''' plt.figure(fig) for i in range(len(LL)): L = LL[i] for X,Y in L: plt.plot(X,Y,'o',color=Col[i],markersize=2) plt.axis('scaled') plt.show() plt.pause(0.0001) ## Création des données 3D G = 5 # Nombre de groupes PPG = 15 # Nombre de points par groupes NP = G*PPG # Nombre de points Largeur = 2 # Largeur groupe +- Lx_3D = [] for g in range(G): X0 = rdi(10,90) Y0 = rdi(10,90) Z0 = rdi(10,90) for p in range(PPG): X = X0 + rdi(-Largeur,Largeur) Y = Y0 + rdi(-Largeur,Largeur) Z = Z0 + rdi(-Largeur,Largeur) Pt = [X,Y,Z] Lx_3D.append(Pt) ''' Erreur Unknown projection 3D Import nécessaire sur certains ordinateurs ''' from mpl_toolkits.mplot3d import Axes3D def Affiche_3D(fig,LL,Col): ''' Affiche chaque liste de la liste LL avec la couleur respective de la liste Col ''' plt.figure(fig) plt.axes(projection="3d") for i in range(len(LL)): L = LL[i] N = len(L) Lx = [L[k][0] for k in range(N)] Ly = [L[k][1] for k in range(N)] Lz = [L[k][2] for k in range(N)] plt.plot(Lx,Ly,Lz,'o',color=Col[i],markersize=2) plt.show() plt.pause(0.0001) ## Choix de l'application Lx = Lx_3D Affiche = Affiche_3D #Affiche(1,[Lx],['r']) ## Algorithme k-moyennes - PARTIE 1 # Question 2 : distance euclidienne x1,x2 def f_Dst(x1,x2): distance = 0 for i in range(len(x1)): distance = distance + (x2[i]-x1[i])**2 return math.sqrt(distance) # Question 3 : centre d'un cluster def f_c(S): dim = len(S[0]) nb_vecteurs = len(S) centre = [0 for i in range(dim)] for i in range(dim): for vect in S: centre[i] = centre[i] + vect[i] centre[i] = centre[i] / nb_vecteurs return centre # Question 4 : Initialisation des centres Lc_init def f_Lc_Init(Lx,k): rd = [] while len(rd) < k: r_n = rdi(0,len(Lx)-1) if r_n not in rd: rd.append(r_n) return [Lx[i] for i in rd] # Question 5 : Etape 1 - Affectation des vecteurs aux clusters # Lc : centres # Lx : vecteurs def f_LS(Lc,Lx): k = len(Lc) LS = [[] for i in range(k)] # Pour chaque vecteur dans Lx # Cherche le centre le plus proche for vi in Lx: # Distance euclidienne vi <-> centres des clusters distances = [f_Dst(vi,Lc[i]) for i in range(k)] # Ajout du vecteur dans le cluster index_k = distances.index(min(distances)) LS[index_k].append(vi) return LS # Question 6 : Etape 2 - Calcul des nouveaux centres des clusters # LS : Liste des clusters def f_Lc(LS): return [f_c(LS[i]) for i in range(len(LS))] # Question 7 : Itérations def f_Iterations(Lx,k): def CheckDelta(delta): ok = True for i in delta: if i > 0.1: ok = False return ok # Tirage au sort des centres des clusters Lc = f_Lc_Init(Lx,k) # Suivi des évolutions des centres norme_centres0 = [np.linalg.norm(Lc[i]) for i in range(k)] # Etape 1 : Affectation des vecteurs aux clusters LS = f_LS(Lc,Lx) # Affiche_2D(0,LS+[Lc], Color+['r']*k) # Etape 2 : Calcul des nouveaux centres Lc = f_Lc(LS) norme_centres = [np.linalg.norm(Lc[i]) for i in range(k)] delta_normes = np.abs(np.array(norme_centres) - np.array(norme_centres0)) i = 0 while CheckDelta(delta_normes) == False: i = i + 1 # Affiche_2D(i,LS+[Lc], Color+['r']*k) norme_centres0 = norme_centres # Etape 1 : Affectation des vecteurs aux clusters LS = f_LS(Lc,Lx) # Etape 2 : Calcul des nouveaux centres Lc = f_Lc(LS) # MAJ des delta normes des centres norme_centres = [np.linalg.norm(Lc[i]) for i in range(k)] delta_normes = np.abs(np.array(norme_centres) - np.array(norme_centres0)) return Lc, LS k=5 Color = [[rdu(0,1), rdu(0,1), rdu(0,1)] for i in range(k)] Lc = f_Lc_Init(Lx_2D,k) LS = f_LS(Lc,Lx_2D) #f_Iterations(Lx_2D,k) ## Algorithme k-moyennes - PARTIE 2 # Question 8 : Affichage image def f_Image(fig,Im): plt.imshow(im) plt.show() # Question 10 : Extraction des pixels en float def f_Extraction_RGB(im): return np.array(np.reshape(im,shape=(im.shape[0]*im.shape[1],3)),dtype=np.float32) # Question 13 : def f_Proximite(Pix,Lc): k = len(Lc) # Distance euclidienne vi <-> centres des clusters distances = [f_Dst(Pix,Lc[i]) for i in range(k)] # Distance minimale index_k = distances.index(min(distances)) return Lc[index_k] # Question 14 : Creation nouvelle image def f_New_Im(im,Lc): l, c, _ = im.shape new_image = im.copy() for i in range(l): for j in range(c): new_image[i,j] = f_Proximite(im[i,j],Lc) return new_image # Question 9 : Ouverture de l'image avion.bmp im = plt.imread("Avion.bmp") #f_Image(im) # Question 11 : Liste Lx Lx = f_Extraction_RGB(im) # Question 12 : Centre initiaux des clusters Lc, LS = f_Iterations(Lx,5) Lc = [[np.float32(113.43473), np.float32(106.26137), np.float32(93.36538)], [np.float32(247.69174), np.float32(247.86427), np.float32(235.7772)], [np.float32(147.30621), np.float32(187.15698), np.float32(213.27867)], [np.float32(210.738), np.float32(190.26212), np.float32(152.66809)], [np.float32(98.593666), np.float32(167.12598), np.float32(216.20789)]] # Question 15 new_img = f_New_Im(im,Lc) f_Image(0,new_img) Color = [[rdu(0,1), rdu(0,1), rdu(0,1)] for i in range(k)] Affiche_3D(0,LS+[Lc],Color+['r']*5)